套路：
物品体积小，背包容量大的题，我们可以采用大范围贪心，小范围DP的办法。
当询问的背包容量超过 V 时，我们选取性价比最低（ ai/i 最小）的物品
直到背包容量降低到比 V 的小的 K，此时直接通过DP得出答案 fK 。

//01背包问题
//二维的做法
#include<bits/stdc++.h>
using namespace std;
int v[1010];
int w[1010];
int f[1010][1010];
int main()
{
	int m,vv;
	cin >>m>>vv;
	for(int i=1;i<=m;i++){
		cin >>v[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=vv;j++){
			f[i][j]=f[i-1][j];
			if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
		}
	}
	cout <<f[m][vv]<<endl;

}
//一维的做法
#include<bits/stdc++.h>
using namespace std;
int v[1010];
int w[1010];
int f[1010];
int main()
{
	int m,vv;
	cin >>m>>vv;
	for(int i=1;i<=m;i++){
		cin >>v[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=vv;j>=v[i];j--){
			f[j]=max(f[j],f[j-v[i]]+w[i]);
		}
	}
	cout <<f[vv]<<endl;

}


//完全背包
//O(n^3)
#include<iostream>
#include<algorithm>
using namespace std;
int v[1010];
int w[1010];
int f[1010][1010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	int m,vv;
	cin >>m>>vv;
	for(int i=1;i<=m;i++){
		cin >>v[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=vv;j++){
			for(int k=0;k*v[i]<=j;k++){
			    f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
			}
		}
	}
	cout <<f[m][vv]<<endl;
	return 0;

}
//优化：O（n^2）
#include<iostream>
#include<algorithm>
using namespace std;
int v[1010];
int w[1010];
int f[1010][1010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	int m,vv;
	cin >>m>>vv;
	for(int i=1;i<=m;i++){
		cin >>v[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=vv;j++){
		    f[i][j]=f[i-1][j];
		    if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
		}
	}
	cout <<f[m][vv]<<endl;
	return 0;
}
//再优化为一维
#include<iostream>
#include<algorithm>
using namespace std;
int v[1010];
int w[1010];
int f[1010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	int m,vv;
	cin >>m>>vv;
	for(int i=1;i<=m;i++){
		cin >>v[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=v[i];j<=vv;j++){
		    f[j]=max(f[j],f[j-v[i]]+w[i]);//max(f[i][j],f[i][j-v[i]]+w[i])因为都是在i行，所以不需要从右向左开始遍历
		    //没有用到i-1层的f值
		}
	}
	cout <<f[vv]<<endl;
	return 0;
}


//多重背包
//暴力写法
#include<iostream>
#include<algorithm>
using namespace std;
int v[110];
int w[110];
int s[110];
int f[110][110];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	int m,vv;
	cin >>m>>vv;
	for(int i=1;i<=m;i++){
		cin >>v[i]>>w[i]>>s[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=vv;j++){
			for(int k=0;k*v[i]<=j&&k<=s[i];k++){
			    f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
			}
		}
	}
	cout <<f[m][vv]<<endl;
	return 0;
}
//二进制优化
#include<iostream>
#include<algorithm>
using namespace std;
int v[25000];//N*log(s),总的拆分数
int w[25000];
int f[25000];
int n,m;
int main()
{
   
	cin >>n>>m;
	int cnt=0;
	for(int i=1;i<=n;i++){
	    int vi,wi,si;
		cin >>vi>>wi>>si;
		int k=1;
		while(k<=si){
		    cnt++;
		    v[cnt]=vi*k;
		    w[cnt]=wi*k;
		    si-=k;
		    k*=2;
		}
		if(si>0){
		    cnt++;
		    v[cnt]=vi*si;
		    w[cnt]=wi*si;
		}
	}	
	n=cnt;
	for(int i=1;i<=n;i++){
	    for(int j=m;j>=v[i];j--){
	        f[j]=max(f[j],f[j-v[i]]+w[i]);
	    }
	}
	cout <<f[m]<<endl;
	return 0;
}


//分组背包
#include<bits/stdc++.h>
using namespace std;
int v[110][110];
int w[110][110];
int s[110];
int f[110];
int main()
{
	int n,m;
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		cin >>s[i];
		for(int j=1;j<=s[i];j++){
		    cin >>v[i][j]>>w[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			for(int k=1;k<=s[i];k++){
			    if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
			}
		}
	}
	cout <<f[m]<<endl;
}


数位dp
//求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和
#include <bits/stdc++.h>
const int N=35,INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;

int K,B;
int f[N][N];

void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j) f[i][j]=1;
            else f[i][j]=f[i-1][j]+f[i-1][j-1];
}

int dp(int n)
{
    if(!n)  return 0;//判断边界
    vector<int> nums;
    while(n) nums.push_back(n%B),n/=B;

    int res=0;//答案
    int last=0;//前缀信息,前面"1"的个数

    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x)//求左边分支中的数个数
        {
            res+=f[i][K-last];
            if(x>1)
            {
                if(K-last-1>=0) res+=f[i][K-last-1];
                break;
            }else 
            {
                last++;
                if(last>K) break;
            }
        }
        if(!i&&last==K) res++;//求右边分支中数的个数
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    
    init();
    
    int l,r;
    cin >>l>>r>>K>>B;
    
    cout <<dp(r)-dp(l-1)<<endl;

    return 0;
}


单调队列优化的DP问题
// 在某两个城市之间有 n 座烽火台，每个烽火台发出信号都有一定的代价。
// 为了使情报准确传递，在连续 m 个烽火台中至少要有一个发出信号。
// 现在输入 n,m 和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少
f[i]表示前1—i座烽火台满足条件，且第i座烽火台点燃的方案集合
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10, INF = 1e9;

int n, m;
int w[N], q[N];
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (q[hh] < i - m) hh ++ ;
        f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    int res = INF;
    for (int i = n - m + 1; i <= n; i ++ ) res = min(res, f[i]);

    printf("%d\n", res);

    return 0;
}
